// 无头结点
#include <iostream>
using namespace std;
template <class T>
class List
{
	struct ListNode // 链表
	{
		T data;
		ListNode* next;
	};
private:
	ListNode* m_list; // 链表
	int m_size;
public:
	List()
	{
		m_list = nullptr;
		m_size = 0;
	}
	List(T data)
	{
		m_list = new ListNode;
		m_list->data = data;
		m_list->next = nullptr;
		m_size = 1;
	}
	~List()
	{
		ListNode* pr = nullptr;
		ListNode* it = m_list;
		while (it != nullptr) // pr 为释放指针，it 为迭代指针，it 为不为空，就把地址交给pr, it去下一个结点，pr释放
		{
			pr = it;
			it = it->next;
			delete pr;
		}
		m_list = nullptr;
		m_size = 0;
	}
public:
	void push_back(T data)
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->next = nullptr;
		if (m_list == nullptr)
		{
			m_list = node;
			m_size++;
			return;
		}
		ListNode* current = m_list;
		while (current->next)
			current = current->next;
		current->next = node;
		m_size++;
	}
	void pop_back()
	{
		if (empty()) // 为空的情况
			return;
		if (m_list->next == nullptr) // 只有一个结点的情况
		{
			delete m_list;
			m_list = nullptr;
			return;
		}
		ListNode* current = m_list->next;
		ListNode* pre = m_list;
		while (current->next != nullptr)
		{
			current = current->next;
			pre = pre->next;
		}
		delete current;
		pre->next = nullptr;
		m_size--;
	}
	void push_front(T data)
	{
		ListNode* node = new ListNode;
		node->data = data;
		node->next = m_list;
		m_list = node;
		m_size++;
	}
	void pop_front()
	{
		if (empty())
			return;
		ListNode* current = m_list;
		m_list = m_list->next;
		delete current;
		m_size--;
	}
	void insert(T data, int pos)
	{
		ListNode* pre = m_list;
		for (int i = 0; i < pos - 1; ++i)
		{
			if (pre == nullptr)
			{
				cout << "越界访问！" << endl;
				exit(-1);
			}
			pre = pre->next;
		}
		ListNode* node = new ListNode;
		node->data = data;
		node->next = pre->next;
		pre->next = node;
		m_size++;
	}
	void erase(T data)
	{
		if (empty())
			return;
		if (m_list->data == data)
		{
			ListNode* current = m_list;
			m_list = m_list->next;
			delete current;
			m_size--;
			return;
		}
		ListNode* pre = m_list;
		while (pre->next != nullptr)
		{
			if (pre->next->data == data)
			{
				ListNode* current = pre->next;
				pre->next = current->next;
				delete current;
				m_size--;
				break;
			}
			pre = pre->next;
		}
	}
	//void eraseAll(T data)
	//{
	//	if (empty()) // 为空的情况
	//		return;
	//	while (m_list->data == data) // 第一个结点就是的情况
	//	{
	//		ListNode* current = m_list;
	//		m_list = m_list->next;
	//		delete current;
	//		m_size--;
	//	}
	//	ListNode* pre = m_list;
	//	while (pre && pre->next) // pre 防止第一个结点为空即被上面删完了，也可以避免下面pre = pre->next存在的特殊情况
	//	{
	//		if(pre->next->data == data)
	//		{
	//			ListNode* current = pre->next;
	//			pre->next = current->next;
	//			delete current;
	//			m_size--;
	//		}
	//		else
	//			pre = pre->next;
	//	}
	//}
	void eraseAll(T data) // 使用虚拟头结点
	{
		if (empty())
			return;
		ListNode* head = new ListNode; // 使用虚拟头结点
		head->next = m_list;
		ListNode* del;
		ListNode* pre = head;
		while (pre->next)
		{
			if (pre->next->data == data)
			{
				del = pre->next;
				pre->next = del->next;
				delete del;
				m_size--;
			}
			else
				pre = pre->next;
		}
		m_list = head->next; // 虚拟头结点的下一位可能已经被删除了，记得将虚拟头结点的下一位还给原来的头结点
		delete head; // 用完记得释放
	}
	void clear()
	{
		ListNode* pr = nullptr;
		ListNode* it = m_list;
		while (it != nullptr)
		{
			pr = it;
			it = it->next;
			delete pr;
		}
		m_list = nullptr;
		m_size = 0;
	}
public:
	bool empty()
	{
		return m_list == nullptr;
	}
	int size()
	{
		return m_size;
	}
	int find(T data)
	{
		ListNode* current = m_list;
		for (int i = 0; i < m_size; ++i)
		{
			if (current->data == data)
				return i;
			current = current->next;
		}
		return -1;
	}
	T& operator[](int pos)
	{
		ListNode* current = m_list;
		for (int i = 0; i < pos; ++i)
		{
			if (current == nullptr)
			{
				cout << "越界访问！" << endl;
				exit(-1);
			}
			current = current->next;
		}
		return current->data;
	}
};
int main()
{
	List<int> list;
	list.push_back(3);
	list.push_back(3);
	list.push_back(1);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(2);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(4);
	list.push_back(3);
	list.eraseAll(3);
	for (int i = 0; i < list.size(); ++i)
		cout << list[i] << " ";
	return 0;
}